package cn.suchan.jianzhi.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author suchan
 * @date 2019/06/18
 */
public class MergeSort {
    /**
     * 负责拆分
     *
     * @param array
     */
    public int[] sort(int[] array) {
        if (array.length <= 1) {
            return array;
        }
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);

        return merge(sort(left), sort(right));
    }

    /**
     * 负责合并
     *
     * @param left
     * @param right
     * @return
     */
    public int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int i = 0, leftIndex = 0, rightIndex = 0;
             i < result.length; i++) {
            if (leftIndex >= left.length) {
                result[i] = right[rightIndex++];
            } else if (rightIndex >= right.length) {
                result[i] = left[leftIndex++];
            } else if (left[leftIndex] < right[rightIndex]) {
                result[i] = left[leftIndex++];
            } else if (right[rightIndex] < left[leftIndex]) {
                result[i] = right[rightIndex++];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        MergeSort sort = new MergeSort();
        int[] sortArray = sort.sort(array);
        for (int i = 0; i < sortArray.length; i++) {
            System.out.printf(sortArray[i] + " ");
        }
    }
}
